package m202405.d25;

import java.util.*;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/5/25 17:01
 */
public class Q22 {

    public static void main(String[] args) {
        Q22 q22 = new Q22();
        List<String> strings = q22.generateParenthesis(2);
        System.out.println();
    }


    Map<Integer, Set<String>> map = new HashMap<>(Map.of(
            1, Set.of("()")
    ));

    public List<String> generateParenthesis(int n) {
        return new ArrayList<>(generateParenthesis1(n));
    }

    public Set<String> generateParenthesis1(int n) {
        Set<String> strings = map.get(n);
        if (strings != null) {
            return strings;
        }
        Set<String> list = new HashSet<>();
        for (int i = 1; i < n; i++) {
            list.addAll(combine(generateParenthesis1(i),generateParenthesis1(n-i)));
        }
        List<String> temp = generateParenthesis(n - 1);
        for (String s : temp) {
            list.add("(" + s + ")");
        }
        map.put(n, list);
        return list;
    }

    private Set<String> combine(Set<String> set1, Set<String> set2) {
        Set<String> rs = new HashSet<>();
        for (String s1 : set1) {
            for (String s2 : set2) {
                rs.add(s1 + s2);
                rs.add(s2 + s1);
            }
        }
        return rs;
    }
}
